class Node {
  constructor (x, y, parent, g=0, h=0) {
    this.x = x, this.y = y
    this.g = g, this.h = h
    this.f = g + h
    this.parent = parent
  }
  
  get_G () {/* 当前节点到起点的代价 */
    if (this.g != 0)
      return this.g
    // 当前节点为起始结点
    else if (this.parent == undefined)
      this.g = 0
    // 当前节点在parent的垂直或水平方向
    else if (this.parent.x == this.x || this.parent.y == this.y)
      this.g = this.parent.get_G() + 10
    // 当前节点在parent的斜对角
    else
      this.g = this.parent.get_G() + 14
    return this.g
  }

  get_H (end) { /* 节点到终点的距离估值 */
    if (this.h == 0)
      this.h = (Math.abs(end[0] - this.x) + Math.abs(end[1] - this.y)) * 10
    return this.h
  }

  get_F (end) { /* 节点的评估值 */
    if (this.f == 0)
      this.f = this.get_G() + this.get_H(end)
    return this.f
  }
}

class MapRoute { /* 使用A*搜索找到最短移动路径 */ 
  constructor (map2d, barrier=1) {
    /*
      :param map2d: 地图
      :param obstruction: 障碍物标记数字
    */
    this.map2d = map2d
    this.barrier = barrier
    // 垂直和水平方向的差向量
    this.v_honv = [[-1, 0], [0, 1], [1, 0], [0, -1]]
    // 斜对角的差向量
    this.v_diag = [[-1, 1], [1, 1], [1, -1], [-1, -1]]
    // 地图边界
    this.x_edge = map2d[0].length, this.y_edge = map2d.length
  }

  is_in_map (x, y) { /* (x, y)是否中地图内 */
    return x >= 0 && x < this.x_edge && y >= 0 && y < this.y_edge
  }

  is_in_closelist (x, y) { /* (x, y) 方格是否在closeList中 */
    return this.closelist[[x, y]] != undefined
  }

  upd_openlist (node) { /* 用node 替换 openlist中的对应数据 */
    this.openlist[[node.x, node.y]] = node
  }

  add_openlist (node) { /* 将node添加到 openlist */
    this.openlist[[node.x, node.y]] = node
  }

  add_closelist (node) { /* 将node添加到 closelist */
    this.closelist[[node.x, node.y]] = node
  }

  pop_minF_openlist () { /* 弹出openlist中F值最小的节点 */
    var key_min = undefined, node_min = undefined
    for (var key in this.openlist){
      if (node_min == undefined)
        key_min = key, node_min = this.openlist[key]
      else if (this.openlist[key].get_F(this.end) < node_min.get_F(this.end))
        key_min = key, node_min = this.openlist[key]
    }
    // 将node_min从openlist中移除
    if (key_min != undefined)
      delete this.openlist[key_min]
    return node_min
  }

  get_Q (P) { /* 找到P周围可以探索的节点 */
    var Q = {}
    // 将水平或垂直方向的相应方格加入到Q
    for (var dir of this.v_honv) {
      var x = P.x + dir[0], y = P.y + dir[1]
      //如果(x,y)不是障碍物并且不在closelist中，将(x,y)加入到Q
      if (this.is_in_map(x, y) 
      && this.map2d[y][x] != this.barrier 
      && !this.is_in_closelist(x, y)) 
        Q[[x,y]] = new Node(x, y, P)
    }
    // 将斜对角的相应方格加入到Q
    for (var dir of this.v_diag) {
      var x = P.x + dir[0], y = P.y + dir[1]
      //如果(x,y)不是障碍物，且(x,y)能够与P联通，且(x,y)不在closelist中，将(x,y)加入到Q
      if (this.is_in_map(x, y) 
      && this.map2d[y][x] != this.barrier
      && this.map2d[P.y][x] != this.barrier
      && this.map2d[y][P.x] != this.barrier
      && !this.is_in_closelist(x, y))
        Q[[x,y]] = new Node(x, y, P)
    }
    return Q
  }

  beginSearch () {
    while(true){
      var P = this.pop_minF_openlist()  // 找到openlist中F值最小的节点作为探索节点
      if (P == undefined) break         // openlist为空，表示没有通向终点的路
      this.add_closelist(P)             // P加入closelist
      var Q = this.get_Q(P)             // P周围待探索的节点
      if (Object.keys(Q).length === 0) continue         // Q中没有任何节点，表示该路径一定不是最短路径，重新从openlist中选择
      if (Q[this.end] != undefined){    //找到了终点， 退出循环
        this.answer = new Node(this.end[0], this.end[1], P)
        break
      }
      for (var key in Q) { // Q中的节点与openlist中的比较
        var node_Q = Q[key]
        var node_openlist = this.openlist[key]
        if (node_openlist == undefined)
          this.add_openlist(node_Q)
        else if (node_Q.get_F(this.end) < node_openlist.get_F(this.end))
          this.upd_openlist(node_Q)
      }
    }
  }

  init (start, end) {
    /*
      :param start: 起点坐标(x,y)
      :param end:   终点坐标(x,y)
    */
    this.start = start
    this.end = end
    this.openlist = {}
    this.closelist = {}
    this.answer = undefined
    
    var node_start = new Node(this.start[0], this.start[1], undefined)
    if(this.map2d[this.start[1]][this.start[0]] == this.barrier){
      var Q
      for(var i = 1; i < 15; i ++ ){
        for(var j = 0; j < 4; j ++ ){
          this.v_honv[j][0] = this.v_honv[j][0] * i
          this.v_diag[j][0] = this.v_diag[j][0] * i
          this.v_honv[j][1] = this.v_honv[j][1] * i
          this.v_diag[j][1] = this.v_diag[j][1] * i
        }
        Q = this.get_Q(node_start)
        for(var j = 0; j < 4; j ++ ){
          this.v_honv[j][0] = this.v_honv[j][0] / i
          this.v_diag[j][0] = this.v_diag[j][0] / i
          this.v_honv[j][1] = this.v_honv[j][1] / i
          this.v_diag[j][1] = this.v_diag[j][1] / i
        }
        if(Object.keys(Q).length !== 0) break
      }

      if(Object.keys(Q).length === 0) return
      for (var key in Q) { // Q中的节点与openlist中的比较
        node_start = Q[key]
        node_start.parent = undefined
        this.start = [node_start.x,node_start.y]
        break
      }
    }
    this.openlist[this.start] = node_start
    this.beginSearch()
  }

  getResult () {
    var node = this.answer
    var answer = []
    while (node != undefined){
      answer.push({x:node.x, y:node.y})
      node = node.parent
    }
    return answer.reverse()
  }
}

module.exports = {
  Node: Node,
  MapRoute: MapRoute
}